Possible answer with a space complexity of O(2N)=O(N):
1) Create 2 stacks, one will hold the values and the other will hold the minimum values.
2) On each push, compare the element with the current min-stack top, push to min-stack if smaller.
3) Pop is always done from both stacks simultaneously
3) Getting the min. value can now be done in O(1) time, just return the min-stack top
אוקטובר 2021
יש כאן בעיה בתשובה שלך. מה קורה אם נניח אני מכניס קודם 1 ואז 2 ואז 3? אז במחסנית המינימום יהיה 1. לאחר מכן נניח אנחנו רוצים לבצע POP לפי מה שרשמת כאן אז מה שיקרה זה שאנחנו נעיף גם את 1 ממחסנית המינימום וגם את 3 מהמחסנית הרגילה וכך יוווצר מצב שבפועל לא הסרנו מהמחסנית הרגילה את 1 אבל הדיווח עליו כמינימום נעלם ממחסנית המינימום.
דצמבר 2023
הPOP במקרה הזה לא יהיה (1)O. זה גם לא נדרש. מה שנרש הוא שהוצאת איבר המינימום יהיה ב(1)O. במקרה ועושים POP, נוציא את האיבר הראשון מהמערך הרגיל, ואת המחסנית שמחזיקה את ערכי המינימום נשפוך לתוך מחסנית עזר עד שנמצא את האיבר שעכשיו הוצאנו מהמחסנית הרגילה(3), נוציא אותו ונחזיר את שאר האיברים מהמחסנית עזר. במקרה הגרוע זה יהיה (N)O
כיצד ניתן למצוא האם שתי רשימות מקושרות שונות מכילות ערכי מספרים כך שסדר הערכים בין שתי הרשימות הוא פולינדרום ? (לדוגמא: רשימה אחת : 1,2,3 רשימה שניה : 3,2,1)
1. שאלה על פרויקט שעשיתי, מה הייתי עושה אם היינו משנים חלק קומפוננטות בתוך הפרויקט
2. שאלה על anagram : נתונות שתי מחרוזות, תכתוב פונקציה שמחליטה אם המחרוזות הן אנאגראמות.תכתוב את הפתרון ב-O(n) זמן ו O(1)) מיקום
נתון buffer מאוד גדול, ממש את הפונקציות malloc ו-free
תשובות
הוסף תשובה
|
לצפיה בתשובות
מרץ 2020
אפשר לעשות רשימה של רשומות אשר מחזיקות מצביע וגודל. אפשר לשכלל את זה לטבלת HASHלפי הכתובות בזיכרון, כך ניתן יהיה לשחרר בסיבוכיות זמן מינימלית ואפשר לשכלל את זה אפילו יותר ע"י אפשרות לקשר את זה עץ מאוזן שממוין לפי המקום הפנוי שבא אחרי המקום המוקצה, כך בזמן הקצאה ניתן יהיה למצוא בזמן לוגריתם את המקום הפנוי הכי קטן שאפשר להקצות מבין המקומות האפשריים ובכך גם להגדיל את סיכויי ההצלחה.
יש מערך בן 98 מקומות שבו מספרים בין 1-100 יש איבר אחד חסר מהו?
תשובות
הוסף תשובה
|
לצפיה בתשובות
פברואר 2020
להכניס את המספרים למערך מונים וכך לגלות את האיבר החסר
פברואר 2021
יש אפשרות טובה יותר
אם חסר 1 לסכום את כל הערכים ואז לבדוק כמה זה פחות 101*50
אם חסר 2 לסכום ולכפול ואז לחשב כנל ולדעת את סכום שני המספרים יחד ואת מכפלת שני הבספרים ולנסו תלראות איזה זוג מספרים מתאים (ככה לא תצטרך לבזז מקום)
ראיון לתפקיד 
